<?php

set_time_limit(0);
// include 'TSPSolver.php';
class GA {
	
	const F				= 0.5;			// Mutation constant; between 0.5..1
	const TRIALS_COUNT 	= 100;
	
	private $data;						// Cities and coordinates
	private $populationSize;			// Population; consists of multiple tours
	private $population;				// Holds population individuals (a.k.a tours)
	private $populationCosts;			// Holds population individuals' costs; acts as buffer
	private $globalDistances;			// Acts as global buffer; distances between cities
	private $optimisation;
	private $tournamentSize;			// Tournament population size
	
	
	public function __construct($optimisation = true) {
		$this->data 			= array();
		$this->population 		= array();
		$this->populationCosts 	= array();
		$this->globalDistances	= array();
		$this->optimisation		= $optimisation;
		$this->tournamentSize	= 10;
	}
	
	public function solve($size = 10) {
		$population = $this->initialisePopulation($size);
		echo 'Fittest: ' . $this->populationCosts[$this->getFittestIndividual()] . PHP_EOL;
		
		$start = microtime(true);
		
		$evolveStart = microtime(true);
		$this->evolve();
		$evolveEnd = microtime(true);
		//echo (microtime(true) - $start) . "\n";die();
		for($i = 0; $i < self::TRIALS_COUNT; $i++) {
			
			if ($i % 25 == 0) {
				echo 'Fittest: ' . $this->populationCosts[$this->getFittestIndividual()] . " Time: " . ($evolveEnd - $evolveStart) . " s" . PHP_EOL;
			}
			
			if ($i % 50 == 0) {
				$this->createSwogFile('TSP_GA_1000_' . $i, $this->population[$this->getFittestIndividual()]);
			}
			
			$evolveStart = microtime(true);
			$this->evolve();
			$evolveEnd = microtime(true);
		}
		
		
		$end = microtime(true);
		
		echo 'Final: ' . $this->populationCosts[$this->getFittestIndividual()] .  PHP_EOL;
		echo 'Time: ' . ($end - $start) . " (sec)" . PHP_EOL;
		//var_dump($this->getFittestIndividual());
		$this->createSwogFile('TSP_GA_1000_5', $this->population[$this->getFittestIndividual()]);
	}
	
	public function initialisePopulation($size = 100, $fittest = null) {
		$this->populationSize = $size;
		
		for($i = 0; $i < $this->populationSize; $i++) {
			$individual = $this->generateIndividual();
			$this->population[$i] = $individual;
			$this->populationCosts[$i] = $this->getRoundTripCost($individual);
		}
		
		return $this->population;
	}
	

	public function evolve() {
		$newPopulation = array();
		$newPopulationCosts = array();
		
		$firstBestIndividuals = 3;
		
		list($bestIndividuals, $bestIndividualsCosts) = $this->getFirstBestIndividuals($firstBestIndividuals); // Last generation best
		
		$newPopulation = array_merge($newPopulation, $bestIndividuals);
		$newPopulationCosts = array_merge($newPopulationCosts, $bestIndividualsCosts);
		
		$child = $this->crossover($newPopulation[0], $newPopulation[1]);
		$newPopulation[$firstBestIndividuals] = $child;
		$newPopulationCosts[$firstBestIndividuals] = $this->getRoundTripCost($child);

		// We can save the fittest! Elitism
		for ($i = $firstBestIndividuals + 1 ; $i < $this->populationSize; $i++) {
			list($parents) = $this->getFittestParents();
			$child = $this->crossover($parents[0], $parents[1]);
			$child = $this->mutate($child);
			$childCost = $this->getRoundTripCost($child);
			$newPopulation[$i] = $child;
		}
		
		for ($i = $firstBestIndividuals + 1; $i < $this->populationSize; $i++) {
			$newPopulationCosts[$i] = $this->getRoundTripCost($newPopulation[$i]);
		}

		$this->population = $newPopulation;
		$this->populationCosts = $newPopulationCosts;
		
		return $this->population;
	}
	
	private function getFirstBestIndividuals($n = 5) {
		$individuals = array();
		$individualsCost = array();
		$found=array();
		for($i = 0; $i < $n; $i++) {
			$currentBest = 999999999;
			
			for($ii = 0; $ii < $this->populationSize; $ii++) {
				if ($this->populationCosts[$ii] < $currentBest && !in_array($ii,$found)) {
					$currentBest = $this->populationCosts[$ii];
					$currentBestIndividual = $ii;
					
				}
			}
			
			$found[] = $currentBestIndividual;
			$individuals[$i] = $this->population[$currentBestIndividual];
			$individualsCost[$i] = $currentBest;
		}
		
		return array($individuals, $individualsCost);
	}
	
	private function getWorstIndividual($population, $populationCosts) {

		$worstIndividuals = array();
		$worstIndividualsCosts = array();
		$found = array();
		for ($j = 0; $j < 2; $j++) {
			$worstIndividualId = rand(0, count($this->population)-1);
			$worstIndividual = $this->population[$worstIndividualId];
			$worstIndividualsCost = $this->populationCosts[$worstIndividualId];
			for ($i = 0; $i < $this->populationSize; $i++) {
					
				if ($this->populationCosts[$i] > $worstIndividualsCost && !in_array($i, $found)) {
					$worstIndividualsCost =  $this->populationCosts[$i];
					$worstIndividualId = $i;
				}
			}
			
			$worstIndividuals[] = $worstIndividualId;
			$worstIndividualsCosts[] = $worstIndividualsCost;
			$found[] = $worstIndividualId;
		}
		
		return array($worstIndividuals, $worstIndividualsCosts);
	}
	private function getFittestParents() {
		$n = 2;
		$parents = array();
		$found = array();
		
		for ($i = 0; $i < $n; $i++) {
			$currentBestIndividualId = rand(0, count($this->population)-1);
			$currentBestIndividual = $this->population[$currentBestIndividualId];
			$currentBest = $this->populationCosts[$currentBestIndividualId];
			for ($j = 0; $j < $this->tournamentSize; $j++) {
				$randomIndividualId = rand(0, $this->populationSize-1);
				
				if ($this->populationCosts[$randomIndividualId] < $currentBest && !in_array($j, $found)) {
					$currentBest = $this->populationCosts[$randomIndividualId];
					$currentBestIndividual = $this->population[$randomIndividualId];
					$currentBestIndividualId = $j;
				}
			}
			
			$parents[] = $currentBestIndividual;
			$found[] = $currentBestIndividualId;
		}
		
		return array($parents);
	}
	
	private function crossover($parent1, $parent2) {
		$child = array();
		$size = count($parent1);
// 		$start = rand(1, $size-2);
// 		$end = rand($start, $size-2);
		
// 		for ($i = 1; $i <= $size; $i++) {
// 			if ($start < $i && $i < $end) {
// 				$child[$i] = $parent1[$i];
// 			}
// 		}
		
// 		for ($i = 1; $i <= $size; $i++) {
// 			if (!isset($child[$i])) {
// 				$child[$i] = $parent2[$i];
// 			}
// 		}

		/* 1. variant */
// 		$crossoverPoint = rand(1, $size-2);
		
		$start = rand(1, $size-2);
		$end = rand($start, $size-2);
		$parent1First = array_slice($parent1, $start, $end, true);
		
// 		$start = rand(1, $size-2);
// 		$end = rand($start, $size-2);
// 		$parent2First = array_slice($parent2,$start, $end, true);
		
		$firstChild = array();
// 		$secondChild = array();
		foreach ($parent1First as $idx) {
			$firstChild[$idx] = $idx;
		}
		
		foreach ($parent2 as $idx) {
			if (!isset($firstChild[$idx])) {
				$firstChild[$idx] = $idx;
			}
		}
		
		return $firstChild;
		
// 		foreach ($parent2First as $idx) {
// 			$secondChild[$idx] = $idx;
// 		}
		
// 		foreach ($parent2 as $idx) {
// 			if (!isset($secondChild[$idx])) {
// 				$secondChild[$idx] = $idx;
// 			}
// 		}
		
// 		$firstCost = $this->getRoundTripCost($firstChild);
// 		$secondCost = $this->getRoundTripCost($secondChild);
		
// 		if ($firstCost <= $secondCost) {
// 			$child = $firstChild;
// 		} else {
// 			$child = $secondChild;
// 		}

		/* 2. variant */
		
// 		$crossoverPoint = rand(1, $size-2);
		//$crossoverPoint = 3;
		
// 		$parent1First = array_slice($parent1, 0, $crossoverPoint, true);
// 		$parent1Second = array_slice($parent1, $crossoverPoint, $size, true);

// 		$parent2First = array_slice($parent2, 0, $crossoverPoint, true);
// 		$parent2Second = array_slice($parent2, $crossoverPoint, $size, true);

		
// 		$child1 = $parent1; // Initially
// 		$child2 = $parent2;

// 		$parent1Values = array_values($child1);
// 		$parent2Values = array_values($child2);
		
// 		for ($i = 0; $i < $crossoverPoint; $i++) {
// 			if ($parent1Values[$i] != $parent2Values[$i]) {
// 				$a = $parent1Values[$i];
// 				$b = $parent2Values[$i];
				
// 				$switched = array();
// 				$temp = $child1[$a];
// 				$child1[$a] = $child1[$b];
// 				$child1[$b] = $temp;
				
// 				foreach($child1 as $idx) {
// 					$switched[$idx] = $idx;
// 				}
				
// 				$child1 = $switched;
// 			}
// 		}
		
// 		for ($i = 0; $i < $crossoverPoint; $i++) {
// 			if ($parent1Values[$i] != $parent2Values[$i]) {
// 				$a = $parent1Values[$i];
// 				$b = $parent2Values[$i];
		
// 				$switched = array();
// 				$temp = $child2[$a];
// 				$child2[$a] = $child2[$b];
// 				$child2[$b] = $temp;
		
// 				foreach($child2 as $idx) {
// 					$switched[$idx] = $idx;
// 				}
		
// 				$child2 = $switched;
// 			}
// 		}

// 		$firstCost = $this->getRoundTripCost($child1);
// 		$secondCost = $this->getRoundTripCost($child2);

// 		if ($firstCost <= $secondCost) {
// 			$child = $child1;
// 		} else {
// 			$child = $child2;
// 		}

		return $child;
	}
	
	private function twoOpt($individual) {
		$bestCost = $this->getRoundTripCost($individual);
		$n = count($individual);
		$start = microtime(true);
		echo 'Before: ' . $bestCost . '<br>';
		for ($i = 1; $i < $n; $i++) {
			$k = $i + 1;

			
			if ($i == 100) {
				die('x');
			}
			while ($k <= $n-1) {
				$first = array_slice($individual, 0, $i, true);
				$second = array_slice($individual, $i, $k, true);
				$second = array_reverse($second, true);
				$last = array_slice($individual, $k, $n, true);
				$newIndividual = $first + $second + $last;
				$newCost = $this->getRoundTripCost($newIndividual);
				
				if ($newCost < $bestCost) {
					$bestCost =  $newCost;
					$individual = $newIndividual;
				}
				
				$k++;
			}
			echo (microtime(true) - $start); die();
		}
		
		echo 'After: ' . $bestCost . '<br>';
		die();
	}
	
	private function mutate($individual) {
		$currentCost = $this->getRoundTripCost($individual);
		$n = count($individual);
		$i = 1;
		
		while ($i <= $n) {			
			$randomNumber = $this->getRandomFloatingPointNumber(0, 1);
			
			if ($randomNumber < self::F) {
				
				$k = rand($i+1, $n-1);
				
				$first = array_slice($individual, 0, $i, true);
				$second = array_slice($individual, $i, $k, true);
				$second = array_reverse($second, true);
				$last = array_slice($individual, $k, $n, true);
				$newIndividual = $first + $second + $last;
				$newCost = $this->getRoundTripCost($newIndividual);
				if ($newCost < $currentCost) {
					$currentCost =  $newCost;
					$individual = $newIndividual;
				}
				
// 				$j = rand(1, $n);
// 				while ($j == $i) {
// 					$j = rand(1, $n);
// 				}
				
// 				$c = rand(1, $n);
// 				while ($c == $i || $c == $j) {
// 					$c = rand(1, $n);
// 				}
				
// 				$d = rand(1, $n);
// 				while ($d == $i || $d == $j || $d == $c) {
// 					$d = rand(1, $n);
// 				}
				
// 				// 4 cities needs to be mutually exclusive;
// 				$costAB = $this->getDistance($i, $j);
// 				$costCD = $this->getDistance($c, $d);
// 				$costAC = $this->getDistance($i, $c);
// 				$costBD = $this->getDistance($j, $d);
				
// 				if ($costAB + $costCD > $costAC + $costBD) {
// 					$switched = array();
// 					$newIndividual = $individual; 
					
// 					$prevJ = $newIndividual[$j];
// 					$newIndividual[$j] = $newIndividual[$c];
// 					$newIndividual[$c] = $prevJ;
	
// 					foreach ($newIndividual as $idx) { // Workaround, No easy way to swicth key=>value pair in PHP
// 						$switched[$idx] = $idx;
// 					}
// 					$newCost = $this->getRoundTripCost($switched);
					
// 					// Accept only better solution
// 					if ($newCost < $currentCost) {
// 						$currentCost = $newCost;
// 						$individual = $switched;
// 					}
// 				}
				
// 				$switched = array();			
				
// 				$j = rand(1, $n);
				
// 				$newIndividual = $individual;
				
// 				$temp = $newIndividual[$i];
// 				$newIndividual[$i] = $newIndividual[$j];
// 				$newIndividual[$j] = $temp;

// 				foreach ($newIndividual as $idx) {
// 					$switched[$idx] = $idx;
// 				}
				
// 				$newCost = $this->getRoundTripCost($switched);
				
// 				// Only swap if best from the current one
// 				if ($newCost < $currentCost) {
// 					$currentCost = $newCost;
// 					$individual = $switched;
// 				}				
			}
			$i++;
		}

		return $individual;
	}
	
	private function getFittestIndividual() {
		$fittest = 0;
		$fittestCost = $this->populationCosts[$fittest];
		
		for ($i = 1; $i < $this->populationSize; $i++) {
			if ($this->populationCosts[$i] < $fittestCost) {
				$fittest = $i;
				$fittestCost = $this->populationCosts[$i];
			}
		}
		
		return $fittest;
	}
	
	private function getTournamentFittest() {
		$fittest = 0;
		$fittestCost = $this->populationCosts[$fittest];
		
		for ($i = 0; $i < $this->tournamentSize; $i++) {
			$randomIndividualId = rand(0, $this->populationSize-1);
			
			if ($this->populationCosts[$randomIndividualId] < $fittestCost) {
				$fittest = $randomIndividualId;
				$fittestCost = $this->populationCosts[$randomIndividualId];
			}
		}
		
		return $this->population[$fittest];
	}
	
	private function getDistance($a, $b) {
		
		return $this->d($this->data[$a], $this->data[$b]);
	}
	
	private function getRoundTripCost($individual) {
		$code = sha1(implode('-', $individual));
		
		if (isset($this->globalDistances[$code])) {

			return $this->globalDistances[$code];
		}
		
		$cost = 0;
		$first = current(array_keys($individual));
		$from = $first;
		foreach ($individual as $to) {
			if ($first == $to) {
				continue;
			}

			$distance = $this->d($this->data[$from], $this->data[$to]);

			$from = $to;
				
			$cost += $distance;
		}

		$distance = $this->d($this->data[$from], $this->data[$first]);
		
		$cost += $distance;
		
		$code2 = sha1(strrev(implode('-', $individual)));
		$this->globalDistances[$code] = $cost;
		$this->globalDistances[$code2] = $cost;
		
		return $cost;
	}
	
	
	// Generates random tour
	private function generateIndividual($nearestNeighbor = true) {
		$individual = array();
		
		if ($nearestNeighbor) {
			$individual = $this->nearestNeighbor();
		} else {
			foreach ($this->data as $city => $coords) {
				$individual[$city] = $city;
			}
			// @FIXME can be improved, 2-opt
			$individual = $this->shuffleAssoc($individual);
		}
		
		return $individual;
	}
	
	private function getNumbrOfCities() {
		
		return count($this->data);
	}
	
	private function getPopulationSize() {
		
		return $this->populationSize;
	}
	
	
	public function read($fileName) {
		$this->fileName = $fileName;
		$file = fopen($fileName . '.txt', 'r');
		$header = fgets($file);
	
		$count = 1;
		while (!feof($file)) {
			$line = fgets($file);
			$row = preg_split('/\s+/', $line);
				
			if (count($row) < 2) {
				break;
			}
				
			$this->data[$count] = array($row[0], $row[1]);
			$count++;
		}
	
		fclose($file);
	}
	
	public function createSwogFile($fileName, $bestSolution) {
		$score = $this->getRoundTripCost($bestSolution);
		$file = fopen($fileName . '.swog', 'w+');
	
		$description = array(
			'new 1100,1100',
			'string 20,20 {Taivo Teder, Genetic Algorithm, Score: ' . $score . '} :tekst',
			'coordsys west south right up',
			'origin 50,50'
		);
		foreach ($description as $line) {
			fwrite($file, $line . PHP_EOL);
		}
	
		foreach ($this->data as $i => $coords) {
			fwrite($file, 'fcircle ' . implode(',', $coords) . ' 3 :p' . $i . PHP_EOL);
		}
	
		$from = current(array_keys($bestSolution));
		$first = $from;
	
		foreach ($bestSolution as $to) {
			fwrite($file, 'line (p' . $from . ') (p' . $to .')' . PHP_EOL);
			$from = $to;
		}
	
		fwrite($file, 'line (p' . $from . ') (p' . $first .')' . PHP_EOL);
	
		fclose($file);
	}
	
	/* Euclidean Distance */
	private function d($a, $b) {
		list($x1, $y1) = $a;
		list($x2, $y2) = $b;
	
		return sqrt(pow($x1 - $x2, 2) + pow($y1 - $y2, 2));
	}
	
	private function nearestNeighbor() {
		// Start from random city
		$start = rand(1, count($this->data));
		
		$unvisited = $this->data;
		$visited = array();
		$node = $start;
		while (count($unvisited) > 0) {
			$visited[$node] = $node;
			$nearest = $this->getNearest($node, $unvisited);
			unset($unvisited[$node]);
			$node = $nearest;
		}
		
		return $visited;
	}
	
	private function getNearest($source, $unvisited) {
		$sourceCoords = $unvisited[$source];
		$distances = array();
		foreach ($unvisited as $node => $coords) {
			if ($node != $source) {
				$distances[$node] = $this->d($sourceCoords, $coords);
			}
		}
	
		asort($distances);
	
		return current(array_keys($distances));;
	}
	
	/* Helper */
	private function shuffleAssoc($array) {
		$shuffled = array();
		$keys = array_keys($array);
		shuffle($keys);
		
		foreach($keys as $key) {
			$shuffled[$key] = $array[$key];
		}
		
		return $shuffled;
	}
	
	private function getRandomFloatingPointNumber($min, $max) {
	
		return $min + mt_rand() / mt_getrandmax() * ($max - $min);
	}
}

$fileName = 'TSP_1000';

$geneticAlgorithm = new GA();
$geneticAlgorithm->read($fileName);
$population = $geneticAlgorithm->solve();
